#include <algorithm>
#include <functional>
#include <queue>
#include <vector>

using namespace std;
class Solution
{
 public:
  // priority_queue 实例默认有一个 vector 容器。函数对象类型 less<T>
  // 是一个默认的排序断言，定义在头文件 function 中，决定了容器中最大的元素会排在队列前面
  priority_queue<int> max_heap;                             // 大根堆
  priority_queue<int, vector<int>, greater<int>> min_heap;  // 小根堆

  // 动态输入，维护两个堆
  void insert(int num)
  {
    max_heap.push(num);
    if (min_heap.size() && max_heap.top() > min_heap.top())  // 交换top
    {
      auto maxv = max_heap.top(), minv = min_heap.top();
      max_heap.pop(), min_heap.pop();
      max_heap.push(minv), min_heap.push(maxv);
    }
    if (max_heap.size() > min_heap.size() + 1)
    {
      min_heap.push(max_heap.top());
      max_heap.pop();
    }
  }

  double getMedian()
  {
    if (max_heap.size() + min_heap.size() & 1) return max_heap.top();  // 如果是奇数
    return (max_heap.top() + min_heap.top()) / 2.0;
  }
};